/***尚硅谷Java数据结构与java算法                  ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***贪心算法             P155                   ***/
/***C++ 实现版本    written by Daniel           ***/

#include <set>
#include <iostream>
#include <string>
#include <map>
#include <list>
#include <algorithm>

using std::cout;
using std::endl;
using std::list;
using std::map;
using std::set;
using std::string;

void printList(list<string> &resList)
{
    for (const auto &item : resList)
    {
        cout << item << "\t";
    }
    cout << endl;
}

int main()
{
    set<string> k1, k2, k3, k4, k5;
    k1.insert("北京");
    k1.insert("上海");
    k1.insert("天津");
    k2.insert("北京");
    k2.insert("广州");
    k2.insert("深圳");
    k3.insert("成都");
    k3.insert("上海");
    k3.insert("杭州");
    k4.insert("上海");
    k4.insert("天津");
    k5.insert("杭州");
    k5.insert("大连");
    map<string, set<string>> broadMap;
    broadMap.insert(std::make_pair("k1", k1));
    broadMap.insert(std::make_pair("k2", k2));
    broadMap.insert(std::make_pair("k3", k3));
    broadMap.insert(std::make_pair("k4", k4));
    broadMap.insert(std::make_pair("k5", k5));
    set<string> total;
    total.insert("北京");
    total.insert("上海");
    total.insert("天津");
    total.insert("广州");
    total.insert("深圳");
    total.insert("成都");
    total.insert("杭州");
    total.insert("大连");
    list<string> resList;
    set<string> tempSet;
    set<string> maxSet;
    string maxStr;
    size_t maxSize = 0;
    while (total.size() != 0)
    {
        
        for (auto item : broadMap)
        {
            //求两个结合的交集，并且把结果储存在tempSet当中
            //insert函数，将迭代器转化为插入迭代器
            std::set_intersection(total.begin(), total.end(), item.second.begin(), item.second.end(), std::inserter(tempSet, tempSet.begin()));
            if (tempSet.size() > maxSize)
            {
                maxStr = item.first;
                maxSize = tempSet.size();
            }
            tempSet.clear();
        }
        maxSize = 0;
        //将结果加入resList
        resList.push_back(maxStr);
        //从total去掉  已经加入的结果
        for (const auto &item : broadMap[maxStr])
        {
            total.erase(item);
        }
    }
    printList(resList);
}